package a07_二叉树;

//二叉树分类
//满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树
public class a11_完全二叉树的节点个数复习2 {

    public static void main(String[] args) {
//        TreeNode root = new TreeNode(1,
//                new TreeNode(2,new TreeNode(4),new TreeNode(5)),
//                new TreeNode(3,new TreeNode(6),null));
        TreeNode root = new TreeNode(1);
        countNodes(root);
    }
    public static int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //判断左子树是不是满二叉树
        int leftNodes = 0;
        if (root.left == null) {
            leftNodes = 0;
        }else {
            TreeNode currentNode = root.left;
            int leftLevel = 1;
            while (currentNode.left != null) {
                currentNode = currentNode.left;
                leftLevel++;
            }
            currentNode = root.left;
            int rightLevel = 1;
            while (currentNode.right != null) {
                currentNode = currentNode.right;
                rightLevel++;
            }
            if(leftLevel == rightLevel){
                //1 1 2<<0 - 1
                //2 3 2<<1 - 1
                //3 7 2<<2 - 1
                leftNodes = (2 << (leftLevel - 1)) - 1;
            }else {
                leftNodes = countNodes(root.left);
            }
        }

        int rightNodes = countNodes(root.right);
        return leftNodes + rightNodes + 1;
    }
}
